package Leetcode.动态规划;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @ClassName 不同路径
 * @since: 2023/9/1 16:53
 * @auth: kirito
 * @description:
 * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
 *
 * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
 *
 * 问总共有多少条不同的路径？
 **/
public class 不同路径 {
    public static void main(String[] args) {
/*        List<List<Integer>> grid = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        list.add(9);
        list.add(5);
        list.add(7);
        list.add(3);
        grid.add(new ArrayList<>(list));
        list.clear();
        list.add(8);
        list.add(9);
        list.add(6);
        list.add(1);
        grid.add(new ArrayList<>(list));
        list.clear();
        list.add(6);
        list.add(7);
        list.add(14);
        list.add(3);
        grid.add(new ArrayList<>(list));
        list.add(2);
        list.add(5);
        list.add(3);
        list.add(1);
        grid.add(new ArrayList<>(list));
        list.clear();

        System.out.println(maxScore2(grid));
        System.out.println(maxScore(grid));*/

    }

    /**
     * 给你一个由 正整数 组成、大小为 m x n 的矩阵 grid。
     * 你可以从矩阵中的任一单元格移动到另一个位于正下方或正右侧的任意单元格（不必相邻）。
     * 从值为 c1 的单元格移动到值为 c2 的单元格的得分为 c2 - c1 。
     *
     * 你可以从 任一 单元格开始，并且必须至少移动一次。
     *
     * 返回你能得到的 最大 总得分。
     *
     * 实质上跟之前的一步一步 和规定方向的题目有点不一样，他不必相邻，且起点任意
     * 那么就相当于找从当前位置往右和右下方向的最大值是多少，然后求其差返回
     * @param grid
     * @return
     */
    public static int maxScore(List<List<Integer>> grid) {
        int ans = Integer.MIN_VALUE;
        int m = grid.size();
        int n = grid.get(0).size();
        int[] dp = new int[n + 1];

        // 初始化dp数组，第一列和第一行初始化为不可能的分数
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = Integer.MAX_VALUE;

        // 遍历网格的每一行
        for (int i = 0; i < m; i++) {
            List<Integer> row = grid.get(i);
            // 遍历网格的每一列
            for (int j = 0; j < n; j++) {
                // 计算当前单元格的左上角和右上角的最小值
                int min = Math.min(dp[j], dp[j + 1]);
                // 获取当前单元格的值
                int x = row.get(j);
                // 更新答案，取当前单元格的值和左上角或右上角的最小值之差的最大值
                ans = Math.max(ans, x - min);
                // 更新dp的当前单元格的值为当前单元格的值和左上角或右上角的最小值中的较小值
                dp[j + 1] = Math.min(min, x);
            }
        }
        System.out.println(Arrays.toString(dp));

        // 返回最大分数
        return ans;
    }
    public static int maxScore2(List<List<Integer>> grid) {
        // 初始化答案为整数最小值，用于后续比较
        int ans = Integer.MIN_VALUE;
        // 获取网格的行数和列数
        int m = grid.size();
        int n = grid.get(0).size();
        // 创建一个二维数组dp，大小为m+1行n+1列
        int[][] dp = new int[m + 1][n + 1];
        // 初始化dp的第一行和第一列为Integer.MAX_VALUE，表示不可能的分数
        Arrays.fill(dp[0], Integer.MAX_VALUE);
        Arrays.fill(dp[1], Integer.MAX_VALUE);
        // 遍历网格的每一行
        for (int i = 0; i < m; i++) {
            // 初始化dp的当前行和第一列为Integer.MAX_VALUE，表示不可能的分数
            dp[i + 1][0] = Integer.MAX_VALUE;
            List<Integer> row = grid.get(i);
            // 遍历网格的每一列
            for (int j = 0; j < n; j++) {
                // 计算当前单元格的左上角和右上角的最小值
                int min = Math.min(dp[i + 1][j], dp[i][j + 1]);
                // 获取当前单元格的值
                int x = row.get(j);
                // 更新答案，取当前单元格的值和左上角或右上角的最小值之差的最大值
                ans = Math.max(ans, x - min);
                // 更新dp的当前单元格的值为当前单元格的值和左上角或右上角的最小值中的较小值
                dp[i + 1][j + 1] = Math.min(min, x);
            }
        }
        for (int i = 0; i < m; i++) {
            System.out.println(Arrays.toString(dp[i]));
        }
        // 返回最大分数
        return ans;
    }

    public int uniquePaths(int m, int n) {
        int[][] dp = new int [m][n];
        for (int i = 0; i < n; i++) dp[0][i] = 1;
        for (int i = 0; i < m; i++) dp[i][0] = 1;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}
